1. Field of the Invention
The present invention generally relates to programmable state machines, and switching networks comprising a plurality of these programmable state machines. More particularly, the present invention is concerned with programmable elements having random access memory (RAM), address inputs, data outputs and feedback paths, and state processors which use matrix switches to network any number of these programmable elements.
2. Description of the Prior Art
The behavior of sequential digital circuits is governed by the inputs to the circuit, and the state of the flip-flops in the circuit at a time T, also known as the present state. From this information the circuit defines a next state at time T+1, where the transition from time T to time T+1 is determined by a common clock source. In some circuits the outputs contribute to the inputs via feedback paths. Therefore, the next state of the circuit is dependent upon the outputs of the circuit at time T as well.
Sequential circuits are generally known as state machines since the order of processing in the circuit can be represented as a state diagram. State machines can perform many useful functions. Indeed, all digital computers are some form of a state machine. However, most computers are not "pure" state machines because they have many features which provide side effects, for example, stacks, interrupts, caches, memory paging, and so on.
Among the classes of processing handled by digital computers is a class known as real-time processing. Real-time data is data which must be processed within some finite processing time T.sub.f. Data not processed within the time bounded by T.sub.f is lost and generally is not recoverable. It is not difficult to see that these time critical processing tasks become more difficult as T.sub.f tends toward zero. Therefore, in real-time systems, as the data input rate increases, all other factors being equal, the burden on computational resources increases to satisfy the fixed time constraint T.sub.f.
Digital communication systems are characterized by the input, output and real-time processing of high-speed data channels, typically receiving megabits of data per second and many modern systems approaching gigabit throughputs. Digital communication is employed because of its well known capacity to overcome problems associated with noisy environments and attenuation. However, digital communication algorithms are computationally intensive and only exacerbate the problem of processing digital data in real-time.
A basic communication channel has one transmitter and one receiver. On the transmitting side of a communication channel, typical functional components of digital transmitters which handle these data include: coders, to encode digital data streams; randomizers (or scramblers) to randomize periodic data; railers, to distribute channels across frequency phase angles such as quadrature phase shift keying (QPSK) modulators; multiplexers, to combine multiple data channels into a single time division multiplexed (TDM) physical channel; and justifiers, to control justification bits which allow synchronization between data channels clocked at various frequencies. A receiver for the same communication channel performs the inverse, or D.sup.5 (decoding, derandomizing, derailing, demultiplexing and dejustification), operations of those functions described above. The digital hardware components which implement these functions are usually designed with sequential circuitry. Oftentimes these circuits are customized for a particular application.
Many communications applications, however, require reconfigurable functional components to satisfy a broad range of operational modes. General purpose computers provide the requisite flexibility for these applications since software can be easily changed to emulate new functions. Nonetheless, such a digital processing capability is not fast enough for real-time processing. On the other hand, fast custom digital circuitry for a reconfigurable system is generally too costly. If implemented in custom circuitry, the vast number of functional configurations and parameter combinations of many nonhomogeneous operational modes quickly becomes a combinatorial explosion of digital circuitry.
Even when the cost of custom circuitry is not prohibitive, the loss of time in fielding state of the art semiconductor processes is a critical shortcoming of complex digital circuitry. Wafer scale technology is providing digital designers undreamed of power in designing functions requiring complex circuitry. Submicron features found on modern wafers lead to extremely dense circuitry, which is therefore lighter and more portable, and faster, since data paths are shortened. The future will bear further increases in circuitry functions as other denser semiconductor processes are discovered.
However, with each new process comes lost time in laying out the existing circuit on a new wafer. The layout requires either a massive, existing library of standard cells, found in silicon compilers, or a tedious and laborious translation from one process to the next. In addition, the new circuit must be retested and this retest is time consuming. Thus, if the smallest and fastest technology is desired to replace a preexisting fielded design, much time is wasted in translating complex circuitry from the old process to the new one.
These problems could be resolved by, instead of designing with complex circuitry, using a large number of simple programmable elements to process in parallel each functional stage of a receiver input. This processing technique is called pipelining and it has been found to be effective in other real-time applications. As a byproduct of using many identical components the system becomes redundant, one processor can take over the function of any other. Thus, design efforts can be minimized, and failures in manufacture or operation can be overcome leading to a highly fault tolerant system.
Although tightly-coupled networks of simple programmable elements have been successfully used in the past for other real-time applications, there are many deficiencies with these networks for use in the currently envisioned application. Most of these networks have limited feedback paths and provide no mechanism for adding additional paths to provide external feedback. In addition, many existing state machine networks are designed with combinational "glue" logic to join together several levels of sequential logic. Furthermore, the switching networks in present applications are typically fixed architecture, being for example, strictly hierarchical, pipeline, array processor or otherwise.
Consequently, a need exists for a programmable, highly reconfigurable, modular, fault tolerant, simple and regular hardware device that can be used to perform real-time communication functions. Such a device should allow a number of feedback paths for state machine processing, minimize levels of circuitry to remove delays, and provide multiple paths between programmable elements for flexible data broadcasting, pipelining, and other parallel architectures.